#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            vector<vector<int>> ans;
            sort(nums.begin(), nums.end());
            int k = 0;
            for (; k < nums.size() - 2; k++) {
                if (nums[k] > 0)
                    break;
                if (k > 0 && nums[k] == nums[k - 1])
                    continue; // 跳过重复值
    
                int l = k + 1;
                int r = nums.size() - 1;
    
                while (l<r) {
                    int sum=0;
                    sum = nums[k] + nums[l] + nums[r];
                    if (sum < 0) {
                        l++;
                    } else if (sum > 0) {
                        r--;
                    } else {
                        ans.emplace_back(vector<int>{nums[k], nums[l], nums[r]});
                        // 去重 l 和 r
                        while (l < r && nums[l] == nums[l + 1])
                            l++;
                        while (l < r && nums[r] == nums[r - 1])
                            r--;
    
                            l++;
                            r--;
                    }
                    
                }
            }
            return ans;
        }
};


void printResult(const vector<vector<int>>& result) {
    cout << "[";
    for (const auto& triplet : result) {
        cout << "[";
        for (int num : triplet) {
            cout << num << ",";
        }
        cout << "\b],"; // \b用来删除最后一个多余的逗号
    }
    cout << "\b]" << endl; // \b用来删除最后一个多余的逗号
}

int main() {

    system("chcp 65001");
    Solution s;
    
    // 测试用例1：标准情况
    vector<int> nums1 = {-1, 0, 1, 2, -1, -4};
    cout << "测试用例1 - 标准情况：" << endl;
    cout << "输入：[-1,0,1,2,-1,-4]" << endl;
    cout << "输出：";
    printResult(s.threeSum(nums1));
    cout << "预期：[[-1,-1,2],[-1,0,1]]" << endl << endl;

    // 测试用例2：全零情况
    vector<int> nums2 = {0, 0, 0, 0};
    cout << "测试用例2 - 全零情况：" << endl;
    cout << "输入：[0,0,0,0]" << endl;
    cout << "输出：";
    printResult(s.threeSum(nums2));
    cout << "预期：[[0,0,0]]" << endl << endl;

    // 测试用例3：无解情况
    vector<int> nums3 = {1, 2, 3, 4, 5};
    cout << "测试用例3 - 无解情况：" << endl;
    cout << "输入：[1,2,3,4,5]" << endl;
    cout << "输出：";
    printResult(s.threeSum(nums3));
    cout << "预期：[]" << endl << endl;

    // 测试用例4：包含重复元素
    vector<int> nums4 = {-2, 0, 0, 2, 2};
    cout << "测试用例4 - 包含重复元素：" << endl;
    cout << "输入：[-2,0,0,2,2]" << endl;
    cout << "输出：";
    printResult(s.threeSum(nums4));
    cout << "预期：[[-2,0,2]]" << endl;

    return 0;
}

